package com.guchenbo.example.dfs;

import java.util.*;

/**
 * @author guchenbo
 * @date 2024/7/29
 */
public class TreeSorter {

    public static List<String> postorder(TreeNode root) {
        Set<String> sorted = new LinkedHashSet<>();
        Set<String> visited = new HashSet<>();
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);

        while (!stack.isEmpty()) {
            TreeNode view = stack.peek();
            List<TreeNode> children = view.getChildren();
            if (visited.contains(view.getName()) || noChild(children)) {
                stack.pop();
                // set 去重
                sorted.add(view.getName());
                continue;
            }
            for (int i = children.size() - 1; i >= 0; i--) {
                stack.push(children.get(i));
            }
            visited.add(view.getName());
        }
        return new ArrayList<>(sorted);
    }

    private static boolean noChild(List<TreeNode> children) {
        return children == null || children.isEmpty();
    }
}
